package aInterview.xiaomi;

class ListNode{
    int  val;
    ListNode next;
    public  ListNode(int val){
        this.val=val;
    }
}

public class RemoveNthListNode {
//TODO:2023/10/17  第一步找打要删除的节点
    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for (int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        ListNode p2 = head;
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2 = p2.next;
            p1 = p1.next;
        }
        // p2 现在指向第 n - k 个节点
        return p2;
    }

    //TODO:2023/10/17 然后再执行删除操作
    // 主函数
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
        ListNode x = findFromEnd(dummy, n + 1);
        // 删掉倒数第 n 个节点
        x.next = x.next.next;
        return dummy.next;
    }


    public   ListNode remove(ListNode head,int N){
        ListNode fast=head;
        int n=0;
        while (n<=N){
            fast=fast.next;
            n++;
        }
        ListNode slow=head;
        while (fast!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return  head;
    }
}
